
/* 
 * File:   main.c
 * Author: felipe
 *
 * Created on 22 de Abril de 2012, 13:12
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h> /*necessario para strcmp()*/
#include <strings.h>
#define MAX 100 //constante

/* prototipo das funcoes */
void insereListaEstado();
//Mealy criaEstado();
//criaSubLista();
void insereSublista();
void insereCadeia();
void insereLista();
void percorreLista();
void insereListaMoore();
void percorreListaMoore();
void copiaLoopsEqv();
//void buscaEqvMoore(); 
//void percorreListaCadeia();

/* estrutura para palavra maquina de Mealy*/
typedef struct NoMealy {
    int estadoAtual; /* estado atual*/
    struct NoSublista *sub; /* ponteiro para sublista*/
    struct NoMealy *prox; /* ponteiro para o proximo elemento da lista */

} NoMealy, *Mealy;

/* inicializando lista de todas os elementos do tipo NoMealy*/
Mealy listaMealy = NULL;

/*estrutura para lista de traduções no idioma destino*/
typedef struct NoSublista {
    char transicao; /* caracter lido */
    int proxEstado; /* o estado de chegada da transicao*/
    char saida; /* a saida gerada por essa transicao*/
    struct NoSublista *prox; /* ponteiro pra proximo elemento da sublista*/

} NoSublista, *Sublista;

/* estrutura da lista de stings*/
typedef struct NoCadeia {
    char cadeia[MAX];
    struct NoCadeia *prox;

} NoCadeia, *Cadeia;
/* inicializando a lista de cadeias*/
Cadeia listaCadeia = NULL;

/* estrutura para lista de elementos do tipo Moore*/
typedef struct NoMoore {
    int estadoAtual;
    char saida;
    int equiv;
    struct NoMoore *prox;
    struct NoSubMoore *subMoore;
} NoMoore, *Moore;

/* inicializando lista de todas os elementos do tipo NoMealy*/
Moore listaMoore = NULL;

/* estrutura para sublista de elementos Moore*/
typedef struct NoSubMoore {
    char transicao;
    struct NoSubMoore *prox;
    struct NoMoore *estadoDestino;
} NoSubMoore, *subMoore;

/* cria elementos da lista*/
Mealy criaEstado(int estadoAtual, char lido, int estadoDestino, char saida) {
    NoMealy *novo, *elem;
    NoSublista *sub, *subelem;
    //sublista
    sub = (NoSublista *) malloc(sizeof (NoSublista));
    sub->transicao = lido;
    sub->proxEstado = estadoDestino;
    sub->saida = saida;
    sub->prox = NULL;
    //lista vazia ou estado atual nao existe na lista de estados
    if (listaMealy == NULL || buscaEstadoAtual(estadoAtual) == 0) {//lista vazia
        //lista principal
        novo = (NoMealy *) malloc(sizeof (NoMealy));
        novo->estadoAtual = estadoAtual;
        novo->prox = NULL;
        novo->sub = sub;
        printf("novo criado = %d->%p->sub: %p, sublido: %c", novo->estadoAtual, novo->prox, novo->sub, novo->sub->transicao);
        insereLista(novo);
    } else {//lista nao-vazia e estado nao encontrado na lista
        for (elem = listaMealy; (elem); elem = elem->prox) {
            if (elem->estadoAtual == estadoAtual) {
                for (subelem = elem->sub; (subelem); subelem = subelem->prox) {
                    if (subelem->prox == NULL) {
                        subelem->prox = sub;
                        sub->prox = NULL;
                    }
                }
            }
        }
    }
    percorreLista();
}

/* cria elemento Moore*/
Moore iniciaMoore() {
    NoMoore *novo;
    char inicio = 'y';
    printf("\nIniciando lista Moore");
    //criando primeiro elemento Moore - obrigatorio (0/y), onde y =  cadeia vazia
    novo = (NoMoore *) malloc(sizeof (NoMoore));
    novo->estadoAtual = 0;
    novo->saida = inicio;
    novo->equiv = 0;
    novo->prox = NULL;
    novo->subMoore = NULL;
    insereListaMoore(novo);
    //percorreListaMoore();
}

NoMoore criaMoore(int estadoAtual, char saida, int equivalencia) {
    NoMoore *novo;
    novo = (NoMoore *) malloc(sizeof (NoMoore));
    novo->estadoAtual = estadoAtual;
    novo->saida = saida;
    novo->equiv = equivalencia;
    novo->prox = NULL;
    novo->subMoore = NULL;
    //insere o elemento criado na lista
    insereListaMoore(novo);
    percorreListaMoore();
    return *novo;
}

void criaSubMoore(NoMoore *moore, char transicao) {
    NoSubMoore *novo;
    novo = (NoSubMoore *) malloc(sizeof (NoSubMoore));
    novo->transicao = transicao;
    novo->prox = NULL;
    novo->estadoDestino = moore;
}

void insereListaMoore(NoMoore *moore) {
    NoMoore *elem;
    int saida = 1;
    //    percorreListaMoore();
    printf("\ninsereListaMoore");
    printf("\natual %d,saida %c,equiv %d,prox %p, sub %p",
            moore->estadoAtual, moore->saida, moore->equiv, moore->prox, moore->subMoore);
    if (!listaMoore) {//lista vazia
        listaMoore = moore;
    } else {//lista nao vazia
        elem = listaMoore;
        if (!elem->prox) {//unico elemento
            elem->prox = moore;
            moore->prox = NULL;
        } else {//mais de um elemento
            for (elem = listaMoore; (elem) && (saida); elem = elem->prox) {
                if (elem->prox && elem->prox->estadoAtual > moore->estadoAtual) {
                    moore->prox = elem->prox;
                    elem->prox = moore;
                    saida = 0;
                }
                if (!elem->prox) {
                    elem->prox = moore;
                    saida = 0;
                }
            }
        }
    }
    printf("\nsaindo da funcao insere lista mooore");
    percorreListaMoore();
}

int buscaListaMoore(int estado) {
    NoMoore *elem;
    for (elem = listaMoore; (elem); elem = elem->prox) {
        if (elem->estadoAtual == estado)
            return 1;
    }
    return 0;
}

void percorreListaMoore() {
    NoMoore *elem;
    NoSubMoore *sub;
    if (listaMoore) {
        for (elem = listaMoore; (elem); elem = elem->prox) {
            printf("\nest-atual:%d, saida: %c, equiv: %d, prox:%p, sub:%p", elem->estadoAtual, elem->saida, elem->equiv, elem->prox, elem->subMoore);
            for (sub = elem->subMoore; (sub); sub = sub->prox) {
                printf("\nSUB:\ntransicao: %c, destino: %d, prox: %p", sub->transicao, sub->estadoDestino->equiv, sub->prox);
            }
        }
    } else {
        printf("lista moore vazia, impossivel percorrer");
    }
}

/* computa as entradas dadas na maquina de Moore*/
void resultcompMoore() {
    NoMoore *moore, *criado, *elem, *elem2;
    NoSubMoore *subMoore, *criadoSub, *sub;
    NoMealy *mealy;
    NoSublista *subMealy;
    int proxEstado, ultimo, ultm2;
    char transicao, saida = 1;
    //ultimo estado da Maquina de Mealy
    ultimo = ultimoEstado();
    ultm2 = ultimoEstado();

    //varre lista de estados
    for (mealy = listaMealy; (mealy); mealy = mealy->prox) {
        for (subMealy = mealy->sub; (subMealy); subMealy = subMealy->prox) {
            if (buscaListaMoore(subMealy->proxEstado)) {//existe estado de mealy na lista moore
                //loop no estado atual - cria-se um novo estado equivalente 
                if (subMealy->proxEstado == mealy->estadoAtual) {
                    ultimo++;
                    criado = (NoMoore *) malloc(sizeof (NoMoore));
                    criado->estadoAtual = ultimo;
                    criado->saida = subMealy->saida;
                    criado->equiv = subMealy->proxEstado;
                    criado->prox = NULL;
                    criado->subMoore = NULL;
                    insereListaMoore(criado);
                    //cria submoore
                    criadoSub = (NoSubMoore *) malloc(sizeof (NoSubMoore));
                    criadoSub->transicao = subMealy->transicao;
                    criadoSub->prox = NULL;
                    criadoSub->estadoDestino = criado;
                    for (moore = listaMoore; (moore); moore = moore->prox) {
                        if (moore->estadoAtual == mealy->estadoAtual) {
                            if (moore->subMoore) {//sublista nao vazia
                                for (subMoore = moore->subMoore; (subMoore->prox); subMoore = subMoore->prox) {
                                }
                                subMoore->prox = criadoSub;
                            } else {//sublista vazia
                                moore->subMoore = criadoSub;
                            }
                        }
                    }
                } else {//nao loop no estado atual mas existe estado em moore
                    //cria submoore
                    criadoSub = (NoSubMoore *) malloc(sizeof (NoSubMoore));
                    criadoSub->transicao = subMealy->transicao;
                    criadoSub->prox = NULL;
                    for (elem = listaMoore; (elem); elem = elem->prox) {//pesquisa estado destino
                        if ((elem->estadoAtual) > ultm2 && elem->equiv == subMealy->proxEstado)
                            criadoSub->estadoDestino = elem;
                    }
                    //criadoSub->estadoDestino = criado;
                    for (moore = listaMoore; (moore); moore = moore->prox) {
                        if (moore->estadoAtual == mealy->estadoAtual) {
                            if (moore->subMoore) {//sublista nao vazia
                                for (subMoore = moore->subMoore; (subMoore->prox); subMoore = subMoore->prox) {
                                }
                                subMoore->prox = criadoSub;
                            } else {//sublista vazia
                                moore->subMoore = criadoSub;
                            }
                        }
                    }
                }
            } else {//nao existe estado - tem q ser criado novo estado
                criado = (NoMoore *) malloc(sizeof (NoMoore));
                criado->estadoAtual = subMealy->proxEstado;
                criado->saida = subMealy->saida;
                criado->equiv = subMealy->proxEstado;
                criado->prox = NULL;
                criado->subMoore = NULL;
                insereListaMoore(criado);
                //cria submoore
                criadoSub = (NoSubMoore *) malloc(sizeof (NoSubMoore));
                criadoSub->transicao = subMealy->transicao;
                criadoSub->prox = NULL;
                criadoSub->estadoDestino = criado;
                //estado deve existir apos insercao acima do mesmo
                for (moore = listaMoore; (moore); moore = moore->prox) {
                    if (moore->estadoAtual == mealy->estadoAtual) {
                        if (moore->subMoore) {//sublista nao vazia
                            for (subMoore = moore->subMoore; (subMoore->prox); subMoore = subMoore->prox) {
                            }
                            subMoore->prox = criadoSub;
                        } else {//sublista vazia
                            moore->subMoore = criadoSub;
                        }
                    }
                }
            }
        }
    }
    copiaLoopsEqv();
    printf("\napos comp moore");
    percorreListaMoore();
}

/* funcao pra copiar os loops dos estados equivalentes*/
void copiaLoopsEqv() {
    NoMoore *elem, *duplicado;
    NoSubMoore *sub;
    int last = ultimoEstado();
    
    for (elem = listaMoore; (elem); elem = elem->prox) {
        for (duplicado = listaMoore; (duplicado); duplicado = duplicado->prox) {
            if (duplicado->estadoAtual > last && duplicado->equiv == elem->estadoAtual) {
                if (elem->subMoore) {//sublista nao vazia
                    duplicado->subMoore = elem->subMoore;
                }
            }
        }
    }

}

Moore buscaEqvMoore(int equiv) {
    NoMoore *elem;
    int ultimo = ultimoEstado();
    for (elem = listaMoore; (elem); elem = elem->prox) {
        if ((elem->estadoAtual) > ultimo && elem->equiv == equiv)
            return elem;
    }
}

NoMoore buscaEstadoMoore(int estado) {
    NoMoore *elem;
    for (elem = listaMoore; (elem); elem = elem->prox) {
        if (elem->estadoAtual == estado)
            return *elem;
    }
}

/* retorna o ultimo estado encontrado na lista de estados de Mealy*/
int ultimoEstado() {
    NoMealy *elem;
    if (listaMealy) {
        for (elem = listaMealy; (elem); elem = elem->prox) {
            if (!elem->prox)
                return elem->estadoAtual;
        }
    } else {
        printf("Lista Mealy vazia - funcao ultimo estado");
    }
}

/* retorna 1 caso o int passado como parametro*/
int buscaEstadoAtual(int estadoAtual) {
    NoMealy *elem;
    if (listaMealy != NULL) {
        for (elem = listaMealy; (elem); elem = elem->prox) {
            if (elem->estadoAtual == estadoAtual)
                return 1;
        }
    }
    return 0;
}

void insereLista(NoMealy * novo) {
    NoMealy *elem, *elem2;
    if (listaMealy != NULL) {
        elem = listaMealy;
        if (elem->prox == NULL)//unico elemento
            elem->prox = novo;
        else {
            for (elem2 = listaMealy; (elem2->prox); elem2 = elem2->prox) {
            }
            elem2->prox = novo;
        }
    } else {
        listaMealy = novo;
    }
}

void criaCadeia(char* cadeia) {
    NoCadeia *nova;
    nova = (NoCadeia *) malloc(sizeof (NoCadeia));
    strcpy(nova->cadeia, cadeia);
    nova->prox = NULL;
    printf("nova cadeia criada:\n");
    printf("\npalavra: %s, prox: %p", nova->cadeia, nova->prox);
    insereCadeia(nova);
    percorreListaCadeia();
}

void insereCadeia(NoCadeia * nova) {
    NoCadeia *elem, *elem2;
    if (listaCadeia != NULL) {
        elem = listaCadeia;
        if (elem->prox == NULL)//unico elemento
            elem->prox = nova;
        else {
            for (elem2 = listaCadeia; (elem2->prox); elem2 = elem2->prox) {
            }
            elem2->prox = nova;
        }
    } else {
        listaCadeia = nova;
    }
}

void percorreLista() {
    NoMealy *elem;
    NoSublista *subelem;
    if (listaMealy != NULL) {
        for (elem = listaMealy; (elem); elem = elem->prox) {
            printf("\n IMPRIMINDO LISTA:");
            printf("\nEstado atual: %d, prox: %p", elem->estadoAtual, elem->prox);
            //sublista
            for (subelem = elem->sub; (subelem); subelem = subelem->prox) {
                printf("\nSUBLISTA:");
                printf("\ntransicao: %c, est_destino: %d, saida: %c\nprox: %p", subelem->transicao, subelem->proxEstado, subelem->saida, subelem->prox);
            }
        }
    } else {
        printf("lista vazia - percorre lista");
    }
}

percorreListaCadeia() {
    NoCadeia *elem;
    if (listaCadeia != NULL) {
        for (elem = listaCadeia; (elem); elem = elem->prox) {
            printf("\nIMPRIMINDO CADEIAS:");
            printf("\ncadeia: %s, prox: %p", elem->cadeia, elem->prox);
        }
    } else {
        printf("\nlista de cadeias vazia");
    }
}

/* computa as entradas na maquina de Mealy*/
void resultCompMealy() {
    NoCadeia *palavra;
    NoSublista *sublista;
    NoMealy *elem;
    int i, estado = 0, saida;
    char j;
    if (listaMealy != NULL && listaCadeia != NULL) {
        printf("\n\nResultado da computacao da Maquina de Mealy:");
        //varre as palavras
        for (palavra = listaCadeia; (palavra); palavra = palavra->prox) {
            printf("\nEntrada - %s\tSaida - ", palavra->cadeia);
            estado = 0;
            //varre os caracteres das palavras
            for (i = 0, j = palavra->cadeia[0]; i < strlen(palavra->cadeia); i++) {
                //varre os estados
                for (elem = listaMealy, saida = 1; (elem) && (saida); elem = elem->prox) {
                    //      printf("procurando estado %d", elem->estadoAtual);
                    if (elem->estadoAtual == estado) {
                        //varre a sublista do estado
                        for (sublista = elem->sub, saida = 1; (sublista) && (saida); sublista = sublista->prox) {
                            if (sublista->transicao == palavra->cadeia[i]) {
                                //printf("\ntransiscao: %c, est_destino: %d, saida: %c", sublista->transicao, sublista->proxEstado, sublista->saida);
                                printf("%c", sublista->saida);
                                estado = sublista->proxEstado;
                                saida = 0;
                            }
                        }
                    }
                }
                j = palavra->cadeia[i + 1];
            }
            estado = 0; //sempre começa a analizar a partir do 0
        }
    } else {
        printf("listas vazias");
    }
}

/* funcao principal */
int main() {
    char alfabeto, saida, prime, cadeia[MAX];
    int estOrigem, estDestino, exit = 0;

    /* leitura dos estados*/
    do {
        printf("\ndigite o estado atual, a transicao, estado destino e a saida gerada\n");
        scanf(" %c", &prime);
        //printf("\nvariavel carac = %c", prime);
        /* verifica se o caractere lido é sustenido - sustenido é delimitador das partes das entrada*/
        if (prime != '#') {
            /* usa a tabela ASCII para corrigir o valor de estado1 q foi lido com caractere*/
            estOrigem = prime - 48;
            scanf(" %c", &alfabeto);
            scanf(" %d", &estDestino);
            scanf(" %c", &saida);
            printf("\nEstado_atual = %d, alfabeto = %c, estado_destino = %d, saida = %c", estOrigem, alfabeto, estDestino, saida);
            printf("\n");
            /* funcao q cria um estado na lista principal*/
            criaEstado(estOrigem, alfabeto, estDestino, saida);
        }
    } while (prime != '#');
    printf("\nfim da leitura dos estados");
    /* leitura das cadeias */
    do {
        printf("\nDigite a cadeia do alfabeto:");
        scanf(" %[^\n]s", cadeia);
        // se o primeiro caractere da string for sust   enido - limitador
        if (cadeia[0] == '#') {
            exit = 1;
            // printf("caractere lido %c", cadeia[0]);
        } else {
            criaCadeia(cadeia);
        }
        //printf("string digitada = %s", cadeia);
    } while (exit != 1);
    printf("\nfim da leitura das cadeias");
    printf("\nInicio da computacao :");
    resultCompMealy(); //ultima a ser mostrada
    iniciaMoore();
    resultcompMoore();
    //saida com sucesso apenas qndo executada a linha abaixo
    return (EXIT_SUCCESS);
}